//给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 
//
// 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [4,6,7,7]
//输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [4,4,3,2,1]
//输出：[[4,4]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 15 
// -100 <= nums[i] <= 100 
// 
// Related Topics 位运算 数组 哈希表 回溯 👍 443 👎 0

package leetcode.editor.cn;

import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution491 {

    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }
    /**
     * 数组，set，map都可以做哈希表，而且数组干的活，map和set都能干，
     * 但如果数值范围小的话能用数组尽量用数组
     */
    public void backTracking(int[] nums, int startIndex){
        if(path.size() > 1)
            result.add(new ArrayList<>(path));
        int[] used = new int[201]; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
        for(int i = startIndex; i < nums.length; i++){
            if((!path.isEmpty() && nums[i] < path.peekLast())
                    || used[nums[i]+100] == 1) continue;
            used[nums[i]+100] = 1;
            path.add(nums[i]);
            backTracking(nums, i+1);
            path.removeLast();
        }
    }

    public void backTracking1(int[] nums, int startIndex){
        if(path.size() > 1)
            result.add(new ArrayList<>(path));
        //本题不能对数组排序，因此不能使用used数组去重
        Set<Integer> set = new HashSet<>(); //使用set对本层进行去重，每一层都会定义一个set
        for(int i = startIndex; i < nums.length; i++){
            if((!path.isEmpty() && nums[i] < path.peekLast())
                || set.contains(nums[i])) continue;
            set.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i+1);
            path.removeLast();
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
